﻿namespace AdvancedTraining.Lesson14;

public class MaxSubArraySumLessOrEqualK
{
    // 请返回arr中，求个子数组的累加和，是<=K的，并且是最大的。
    // 返回这个最大的累加和
    public static int GetMaxLessOrEqualK(int[] arr, int k)
    {
        // 记录i之前的，前缀和，按照有序表组织
        var set = new SortedSet<int> { 0 }; // 一个数也没有的时候，就已经有一个前缀和是0了
        var max = int.MinValue;
        var sum = 0;
        // 每一步的i，都求子数组必须以i结尾的情况下，求个子数组的累加和，是<=K的，并且是最大的
        foreach (var item in arr)
        {
            sum += item; // sum -> arr[0..i];

            // 找到set中 >= sum - k 的最小值
            var target = sum - k;
            var view = set.GetViewBetween(target, int.MaxValue);
            if (view.Count > 0)
            {
                var ceiling = view.FirstOrDefault();
                max = Math.Max(max, sum - ceiling);
            }

            set.Add(sum); // 当前的前缀和加入到set中去
        }

        return max;
    }

    /// <summary>
    /// 测试最大子数组累加和不超过K的算法
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("最大子数组累加和<=K算法测试开始");

        // 测试用例1: 基本测试
        Console.WriteLine("测试用例1: 基本测试");
        var arr1 = new int[] { 1, 2, 3, 4, 5 };
        var k1 = 11;
        var result1 = GetMaxLessOrEqualK(arr1, k1);
        Console.WriteLine($"数组: [{string.Join(", ", arr1)}], K={k1}");
        Console.WriteLine($"结果: {result1}");
        Console.WriteLine("期望: 11 (1+2+3+4 或 2+3+4 或 1+2+3+5)");

        // 测试用例2: 包含负数
        Console.WriteLine("\n测试用例2: 包含负数");
        var arr2 = new int[] { 2, -1, 2, -3, 4, 1 };
        var k2 = 5;
        var result2 = GetMaxLessOrEqualK(arr2, k2);
        Console.WriteLine($"数组: [{string.Join(", ", arr2)}], K={k2}");
        Console.WriteLine($"结果: {result2}");
        Console.WriteLine("期望: 5 (2-1+2+2 或 4+1)");

        // 测试用例3: 所有数都大于K
        Console.WriteLine("\n测试用例3: 所有数都大于K");
        var arr3 = new int[] { 6, 7, 8, 9 };
        var k3 = 5;
        var result3 = GetMaxLessOrEqualK(arr3, k3);
        Console.WriteLine($"数组: [{string.Join(", ", arr3)}], K={k3}");
        Console.WriteLine($"结果: {result3}");
        Console.WriteLine("期望: 负数或最小值（因为没有符合条件的子数组）");

        // 测试用例4: 空数组
        Console.WriteLine("\n测试用例4: 空数组");
        var arr4 = new int[] { };
        var k4 = 10;
        var result4 = GetMaxLessOrEqualK(arr4, k4);
        Console.WriteLine($"数组: [], K={k4}");
        Console.WriteLine($"结果: {result4}");
        Console.WriteLine("期望: 负数或最小值（空数组无子数组）");

        // 测试用例5: 单个元素
        Console.WriteLine("\n测试用例5: 单个元素");
        var arr5 = new int[] { 3 };
        var k5 = 5;
        var result5 = GetMaxLessOrEqualK(arr5, k5);
        Console.WriteLine($"数组: [{string.Join(", ", arr5)}], K={k5}");
        Console.WriteLine($"结果: {result5}");
        Console.WriteLine("期望: 3");

        // 测试用例6: K=0的特殊情况
        Console.WriteLine("\n测试用例6: K=0的特殊情况");
        var arr6 = new int[] { -2, -1, 3, 4, -5 };
        var k6 = 0;
        var result6 = GetMaxLessOrEqualK(arr6, k6);
        Console.WriteLine($"数组: [{string.Join(", ", arr6)}], K={k6}");
        Console.WriteLine($"结果: {result6}");
        Console.WriteLine("期望: 0 (空子数组)");

        // 测试用例7: 全负数数组
        Console.WriteLine("\n测试用例7: 全负数数组");
        var arr7 = new int[] { -1, -2, -3, -4 };
        var k7 = -2;
        var result7 = GetMaxLessOrEqualK(arr7, k7);
        Console.WriteLine($"数组: [{string.Join(", ", arr7)}], K={k7}");
        Console.WriteLine($"结果: {result7}");
        Console.WriteLine("期望: -2 或 -1");

        // 测试用例8: 复杂数组
        Console.WriteLine("\n测试用例8: 复杂数组");
        var arr8 = new int[] { 5, -2, 3, -1, 2, -4, 6, -3 };
        var k8 = 8;
        var result8 = GetMaxLessOrEqualK(arr8, k8);
        Console.WriteLine($"数组: [{string.Join(", ", arr8)}], K={k8}");
        Console.WriteLine($"结果: {result8}");
        Console.WriteLine("手动验证可能的子数组:");
        Console.WriteLine("[5, -2, 3, -1, 2] = 7");
        Console.WriteLine("[5, -2, 3] = 6");
        Console.WriteLine("[3, -1, 2, -4, 6] = 6");
        Console.WriteLine("[6] = 6");
        Console.WriteLine("[5, -2, 3, -1, 2, -4, 6] = 9 > 8");
        Console.WriteLine("看起来结果7是正确的");

        Console.WriteLine("\n最大子数组累加和<=K算法测试结束");
    }
}